#include "bitree.h"

typedef struct BiTreeNode_tag{
	void*		data;

	BiTreeNode*	left;
	BiTreeNode*	right;
}BiTreeNode;

typedef struct BiTree_tag{
	int size;

	int (*compare)(const void* key1, const void* key2);
	void (*destroy)(void* data);

	BiTreeNode* root;
}BiTree;

/*
The bitree_create operation initializes a binary tree so that it can be used in other
operations (see Example 9-2). Initializing a binary tree is a simple operation in
which we set the size member of the tree to 0, the destroy member to
destroy, and the root pointer to NULL.
The runtime complexity ofbitree_createis O(1) because all of the steps in initializing 
a binary tree run in a constant amount of time.
*/
BiTree* bitree_create(void (*destroy)(void* data))
{
	BiTree* tree;
	assert(NULL != (tree= (BiTree* )malloc(sizeof(BiTree))));

	tree->destroy = destroy;
	tree->size = 0;
	tree->root = NULL;

	return tree;
}

/*
The bitree_destroy operation destroys a binary tree (see Example 9-2). Primarily
this means removing all nodes from the tree. The function passed as destroy to
bitree_createis called once for each node as it is removed, provided destroy was
not set to NULL.
The runtime complexity ofbitree_destroyis O(n), where n is the number of nodes
in the binary tree. This is because bitree_destroysimply calls bitree_rem_left, which
runs inO(n) time, where n is the number of nodes in the tree.
*/
void bitree_destroy(BiTree* tree)
{
	bitree_rmv_left(tree,NULL);
	free(tree);
	tree= NULL;
}
/*
Thebitree_ins_leftoperation inserts a node into a binary tree as the left child of a
specified node (see Example 9-2). The call sets the new node to point to the data
passed by the caller. Linking the new node into the tree is accomplished by setting 
the left pointer of node to point to the new node. If node is NULL and the
tree is empty, we set the root member of the tree data structure to the new node.
We update the size of the tree by incrementing the size member.
The runtime complexity of bitree_ins_left is O(1) because all of the steps in inserting 
a node into a binary tree run in a constant amount of time.
*/
int bitree_ins_left(BiTree* tree, BiTreeNode* node, const void* data)
{
	BiTreeNode* new_node;
	assert(NULL != tree);
	if (NULL == (new_node = (BiTreeNode* )malloc(sizeof(BiTreeNode))))
		return -1;
	new_node->data = (void* )data;
	if (NULL == node && tree->size == 0)
	{
		new_node->left = NULL;
		new_node->right = NULL;
		tree->root = new_node;
	}
	else
	{
		assert(NULL != node);
		assert(NULL == node->left);
		new_node->left = NULL;
		new_node->right = NULL;
		node->left = new_node;
	}

	tree->size++;

	return 0;
}
/*
Thebitree_ins_rightoperation inserts a node into a binary tree as the right child of
a specified node (see Example 9-2). This operation works similarly tobitree_ins_
left, except that linking the new node into the tree is accomplished by setting the
rightpointer ofnodeto point to the new node.
The runtime complexity ofbitree_ins_right is O(1) because all of the steps in
inserting a node into a binary tree run in a constant amount of time.
*/
int bitree_ins_right(BiTree* tree, BiTreeNode* node, const void* data)
{
	BiTreeNode* new_node;
	assert(NULL != tree);
	if (NULL == (new_node = (BiTreeNode* )malloc(sizeof(BiTreeNode))))
		return -1;

	new_node->data = (void* )data;
	if (NULL == node && tree->size == 0)
	{
		new_node->left = NULL;
		new_node->right = NULL;
		tree->root = new_node;
	}
	else
	{
		assert(NULL != node);
		assert(NULL == node->right);
		new_node->left = NULL;
		new_node->right = NULL;
		node->right = new_node;
	}

	tree->size++;

	return 0;
}
/*
Thebitree_rem_leftoperation removes the subitree rooted at the left child of a
specified node (see Example 9-2). Nodes are removed by performing a postorder
traversal beginning at the left child of node.Ifnodeis NULL, we begin the 
traversal at the root node. The function passed asdestroyto bitree_createis called
once for each node as it is removed, provideddestroywas not set to NULL. As
each node is removed, we update thesizemember of the tree data structure as
well.
The runtime complexity ofbitree_rem_left is O(n), where nis the number of
nodes in the subitree rooted at the left child ofnode. This is because bitree_rem_
left performs a postorder traversal to visit each of the nodes in the subitree while
all other parts of the operation run in a constant amount of time.
*/
void bitree_rmv_left(BiTree* tree, BiTreeNode* node)
{
	BiTreeNode **old_node;
	assert(NULL != tree && tree->size>0);
	if(node == NULL)
		old_node = &tree->root;
	else
		old_node = &node->left;

	if ((*old_node) != NULL)
	{
		bitree_rmv_left(tree, (*old_node));
		bitree_rmv_right(tree, (*old_node));

		tree->destroy((*old_node)->data);

		free((*old_node));
		*old_node = NULL;
		if(NULL != node)
			node->left = NULL;
		tree->size--;
	}
}
/*
Thebitree_rem_rightoperation removes the subitree rooted at the right child of a
specified node (see Example 9-2). This operation works much likebitree_rem_left,
except that nodes are removed by performing a postorder traversal beginning at
the right child of node.
The runtime complexity ofbitree_rem_rightis O(n), where nis the number of
nodes in the subitree rooted at the right child ofnode. This is because bitree_rem_
rightperforms a postorder traversal to visit each of the nodes in the subitree while
all other parts of the operation run in a constant amount of time.
*/
void bitree_rmv_right(BiTree* tree, BiTreeNode* node)
{
	BiTreeNode **old_node;
	assert(NULL != tree && tree->size>0);
	if(node == NULL)
		old_node = &tree->root;
	else
		old_node = &node->right;

	if ((*old_node) != NULL)
	{
		bitree_rmv_left(tree, (*old_node));
		bitree_rmv_right(tree, (*old_node));

		tree->destroy((*old_node)->data);

		free((*old_node));
		if(NULL != node)
			node->right = NULL;
		tree->size--;
	}
}
/*
Thebitree_mergeoperation merges two binary trees into a single binary tree (see
Example 9-2). First, we initializ emerge by callingbitree_create. Next, we insert data
into the merged tree at its root. The merged tree's left and right children are then
set to be the root nodes ofleftandright, and the size of the tree is adjusted to
reflect the sizes of the subitrees. Last, we detach the nodes now in the merged tree
from the original trees and set the size of each tree to 0.
The runtime complexity ofbitree_mergeis O(1) because all of the steps in merging two 
binary trees run in a constant amount of time.
*/
int bitree_merge(BiTree* merge, BiTree* left, BiTree* right, const void* data)
{
	assert(NULL != left && NULL != right);

	merge = bitree_create(left->destroy);

	if(bitree_ins_left(merge, NULL, (void* )data)  != 0)
		return -1;

	merge->root->left = left->root;
	merge->root->right = right->root;
	merge->size = merge->size + left->size +right->size;

	free(left);
	free(right);

	return 0;
}
int bitree_size(const BiTree* tree)
{
	return tree->size;
}
BiTreeNode* bitree_root(const BiTree* tree)
{
	return tree->root;
}
int bitree_is_eob(const BiTreeNode* node)
{
	return (node == NULL);
}
int bitree_is_leaf(const BiTreeNode* node)
{
	return (node->left == NULL && node->right == NULL ? 1 :0);
}
void* bitree_data(const BiTreeNode* node)
{
	return node->data;
}
BiTreeNode* bitree_left(const BiTreeNode* node)
{
	return node->left;
}
BiTreeNode* bitree_right(const BiTreeNode* node)
{
	return node->right;
}


void bitree_debug(const BiTree* tree)
{
	if (tree->size > 0)
	{
		printf("tree->size = %d \n", tree->size);
		printf("*(tree->root->data) = %d\n", *((int *)(tree->root->data)));
		if (tree->root->left != NULL)
		{
			printf("*(tree->root->left->data) = %d\n", *((int *)(tree->root->left->data)));
		}

		if (tree->root->right != NULL)
		{
			printf("*(tree->root->right->data) = %d\n", *((int *)(tree->root->right->data)));
		}
	}
}